
\chapter{Proposta de trabalho}

A implementação do ambiente de desenvolvimento de software, de acordo com os
requisitos explicitados na seção \ref{s:plataforma_desenvolvimento}, requer uma
composição de ferramentas que trabalham em conjunto para prover esse suporte.
Para identificar as ferramentas necessárias, são apresentados dois fluxogramas
tradicionais de desenvolvimento para um sistema embarcado, em um projeto que
utiliza um misto de código C e assembly. O primeiro diz respeito ao processo de
compilação de código, enquanto o segundo exemplifica o processo de execução,
depuração e otimização do programa.

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.4]{images/fluxograma-desenvolvimento_software}
  \textsf{\caption{Fluxo tradicional de compilação de software misto C e
                   assembly}}
  \label{fig:fluxo_desenvolvimento}
\end{figure}

A fig. \ref{fig:fluxo_desenvolvimento} mostra o modelo tradicional de compilação
de software, uma extensão do fluxograma proposto em \cite{vahid_book}. Foi
convencionado que o projeto em questão é constituído por 2 códigos-fonte C
(\texttt{A.c} e \texttt{B.c}) e 1 arquivo de código fonte assembly
(\texttt{C.asm}). A primeira consideração a ser feita é que este processo
utiliza a técnica de \textit{compilação cruzada}. O desenvolvedor cria o código
fonte e o compila em uma máquina host, possivelmente um desktop comum. O arquivo
binário final gerado, entretanto, contêm instruções correspondentes ao
processador alvo do sistema embarcado. Esta é uma abordagem bastante comum.
Nestes casos, diz-se que o compilador é um \textit{compilador cruzado}
(de \textit{cross-compiler}).  O fluxo completo de compilação é:

\begin{enumerate}
\item O programador cria, com um editor de texto comum, os arquivos de
\textit{código fonte}.

\item Um \textit{compilador} C é executado, tendo como entrada os códigos fonte
em C. Ele é responsável por traduzir o código desta linguagem alto nível para
uma representação mais próxima do código binário interpretado pela máquina
(assembly). No caso, este modelo apresenta uma simplificação do processo, onde o
compilador gera arquivos assembly explícitos. Na prática, este processo é
transparente para o usuário, e o compilador age como montador e ligador em uma
mesma invocação.

\item O \textit{montador} é executado, tendo como entrada os arquivos de código
fonte assembly originais e os gerados pelo compilador C. O montador é
responsável por interpretar esta representação textual do assembly, que é uma
linguagem de programação simples, e por traduzi-la para um formato de código
binário relocável.

\item Neste momento, há um conjunto de arquivos independentes com código
binário, cada um constituindo uma unidade de compilação diferente. Além dos
arquivos originais que o programador usou como entrada, ainda são utilizados os
códigos binários da biblioteca padrão da linguagem.

\item O \textit{ligador} é executado, tendo como entrada todos os arquivos de
código binário. Neste momento, as referências a símbolos externos presentes em
cada unidade de código são resolvidas, e um único arquivo binário é criado,
contendo o executável final.

\item O \textit{arquivo executável} final está pronto, e pode ser utilizado para
executar o programa que foi descrito com o código fonte original.
\end{enumerate}





\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.45]{images/fluxograma-execucao_software}
  \textsf{\caption{Fluxo tradicional de execução, depuração e otimização de
                   software}}
  \label{fig:fluxo_execucao}
\end{figure}

O processo usual de execução, depuração e/ou otimização do código é representado
na fig. \ref{fig:fluxo_execucao}. O fluxo de atividades é:

\begin{enumerate}
\item Primeiramente, a versão atual do código fonte é compilada, através do
processo apresentado anteriormente, e o código binário executável é gerado
novamente.

\item Um programa denominado \textit{carregador} é executado, tendo como entrada
o arquivo executável. Este programa é responsável por carregar a imagem estática
do programa na memória do dispositivo, preparando-o para sua execução. 
  
\item O programa é executado no dispositivo. Note que o dispositivo, neste
contexto, não é necessariamente o sistema embarcado em si. Pode ser um protótipo
contendo somente alguns componentes, ou até um software simulador da arquitetura
do SE.
  
\item Os dados de saída do software, de acordo com as suas respectivas entradas,
são utilizados para realizar correções no código fonte (depuração) ou
modificações com o intuito de melhorar a eficiência do programa (otimização). Em
ambos, caso alguma modificação precise ser feita, o processo é reiniciado e o
código fonte é recompilado. 
\end{enumerate}

Estes dois processos de desenvolvimento, que se aplicam não somente a sistemas
embarcados como também a programação desktop mais usual, indicam o conjunto de
ferramentas necessário para o ambiente de programação do RISCO: editor de
código, compilador, montador, ligador, carregador, o dispositivo e um
depurador.

Deste conjunto podemos descartar alguns componentes. O editor de código, sendo
executado no ambiente host, não apresenta nenhuma particularidade relativa ao
processador RISCO. Ou seja, é possível utilizar qualquer editor de texto normal.
O depurador (\textit{debugger}) não é um item estritamente necessário, levando
em conta o escopo deste trabalho. O dispositivo que representa o sistema
embarcado contendo o processador RISCO, assim como o seu carregador de código,
podem assumir basicamente 3 formas diferentes:

\begin{itemize}
\item \textit{Dispositivo real}: o código é executado em um equipamento físico
real, um SE baseado em processador RISCO. Neste caso, o carregador é um software
capaz de se comunicar com o dispositivo externo e carregar o código em sua
memória. Como exemplo disto, pode-se citar um FPGA programado para
simular um processador RISCO.

\item \textit{Especificação executável}: uma técnica comum para prototipagem
rápida de sistemas é utilizar uma linguagem de especificação de hardware que
seja executável, possibilitando que um software especializado realize uma
simulação de alta fidelidade. Neste caso, o carregador é um módulo particular
deste software, responsável por incluir o código executável na representação
interna da memória do circuito. Um exemplo desta forma são ferramentas de
simulação VHDL.

\item \textit{Simulador artificial}: neste caso, o dispositivo é representado
por um software, escrito em uma linguagem de programação de alto nível,
responsável por ler um arquivo binário executável de entrada e executar suas
instruções uma a uma, de modo que os efeitos colaterais são observados na
máquina host. Em geral, simuladores deste tipo apresentam performance superior
aos outros 2. Isto decorre do fato de que esse simulador tem o privilégio de ser
executado na máquina de desenvolvimento do código, que comumente tem uma
performance muito superior a do sistema embarcado. Neste caso, o carregador é
simplesmente um módulo interno do simulador. 
\end{itemize}










Com relação ao RISCO, levando em conta o trabalho existente, iremos estender a
descrição VHDL para suportar a execução de programas via uma especificação
executável. Além disso, pretende-se implementar um simulador artificial, devido
as suas vantagens particulares.

Nas seções \ref{s:compilador}, \ref{s:montador} e \ref{s:simulador}, destacamos
cada componente a ser implementado e discutimos propostas para o seu
desenvolvimento.


\section{Compilador}
\label{s:compilador}

O estudo do projeto e da implementação de compiladores forma uma área distinta
dentro da Ciência da Computação como um todo. \citeonline{dragon_book}
mostra que esta classe de programas apresenta propriedades e desafios únicos a
este nicho. Um compilador funcional deve ser capaz de entender a organização
sintática e semântica de uma linguagem de programação real, e ser capaz de
aplicar transformações em representações do código, preservando o seu sentido e
traduzindo-o para uma outra representação.

É um consenso que a implementação completa de um compilador robusto e de boa
qualidade para uma linguagem real é uma tarefa árdua e complexa. As ferramentas
de compilação mais populares hoje em dia, sejam as comerciais ou de código
aberto, fazem parte de projetos que já acumulam anos de duração. No escopo deste
trabalho, a realidade é que é impossível conceber o desenvolvimento de um
compilador completo e robusto para o RISCO, levando-se em consideração as
restrições de tempo e recursos disponíveis.

Devido às restrições e requisitos envolvidos, foi decidido que o compilador
desta plataforma de desenvolvimento será uma extensão de um compilador já
existente. Isto é, iremos reutilizar o código de um projeto já consolidado e que
está sendo utilizado atualmente, o modificaremos para incluir o suporte a
geração de código para o assembly do processador RISCO. Mais especificamente,
iremos aproveitar:

\begin{itemize}
\item \textit{Módulos da camada superior} (\textit{front-end}): analisador
léxico e analisador sintático. Note que, caso o código do compilador preze
pelo baixo acoplamento entre componentes, seguindo práticas moderna de
engenharia de software, tais módulos só dependem da especificação da linguagem
de programação sendo compilada, e não da sua arquitetura alvo.

\item \textit{Linguagem de representação intermediária} (IR): os compiladores
modernos utilizam uma linguagem privada, interna ao compilador, para representar
o código de forma compacta e poder aplicar transformações nesta representação de
forma eficiente. Esta linguagem só depende da linguagem de programação original
e da implementação dos passos de transformação no compilador, e não
necessariamente precisa refletir características do alvo.

\item \textit{Módulos de otimização}: em um compilador modular, os passos de
otimização são bem definidos e trabalham somente sobre a linguagem de
representação intermediária (ou entre vários dialetos dela). Deste modo, é
possível reutilizar estes componentes.

\item \textit{Componentes genéricos de geração de código}: o processo de geração
de código em um compilador é bastante complexo e dependente da arquitetura alvo.
Entretanto, algumas transformações e algoritmos utilizados podem ser abstraídos,
se tornando módulos genéricos. Como exemplos disto, temos os algoritmos de
escolha da instruções e alocação de registradores.
\end{itemize}

O código de extensão a ser desenvolvido fará parte dos módulos na camada
inferior do compilador (\textit{back-end}). Basicamente, será um módulo
responsável por incluir as definições do assembly do RISCO, assim como as suas
particularidades, dentro do \textit{framework} utilizado pelo compilador. Tal
módulo será incluído em meio aos componentes genéricos de geração de código,
fazendo parte do processo de compilação. O trabalho irá envolver, acima de tudo,
o entendimento da arquitetura geral do compilador envolvido, assim como dos
detalhes do processo de geração de código.

A primeira parte do trabalho será, portanto, a escolha do compilador que será
utilizado para implementação deste suporte. Durante o período de elaboração
desta proposta, foi realizada uma pesquisa breve com relação aos compiladores de
código aberto mais populares para a linguagem C, as suas documentações
disponíveis, assim como o cenário atual de ascenção de novos projetos. A
conclusão foi de que existem duas tendências de caminho claras para um
desenvolvedor procurando contribuir com um projeto de um compilador C real.
Estas duas tendências são representadas pelo compilador \textit{GCC}, parte da
coleção de compiladores GNU, e pelo compilador \textit{Clang}, parte do projeto
LLVM. As duas opções serão analisadas brevemente em \ref{ss:gcc} e
\ref{ss:llvm}, e a escolha final será tomada no início do desenvolvimento do
trabalho aqui proposto.

\subsection{GCC}
\label{ss:gcc}

O GCC (\citeyear{gcc_site}) é o acrônimo coloquial pelo qual o compilador C da
coleção de compiladores GNU (\textit{GNU Compiler Collection}) é conhecido. Esta
convenção surgiu devido ao fato de que o nome do binário invocado para a
execução do compilador C é ``\texttt{gcc}''. Trata-se do compilador oficial na
grande maioria dos sistemas operacionais baseados no GNU/Linux. Apesar da sua
marca estar fortemente associada ao desenvolvimento tradicional de software C em
sistemas Unix, a coleção de compiladores GNU é bastante vasta e o seu código
visa a portabilidade para diversas arquiteturas diferentes. De fato, ele foi
portado para mais arquiteturas diferentes do que qualquer outro compilador
em uso.

O GCC apresenta, indiscutivelmente, uma das melhores, senão a melhor,
eficiência no campo de geração e otimização de código. Trata-se de um projeto
antigo, cuja primeira versão foi lançada em \citeyear{gcc_site}, e que desde
então é um dos principais compiladores C existentes.

A principal desvantagem na utilização do GCC para a implementação de um novo
back-end, conforme visto anteriormente, é que devido a idade da sua base de
código, assim como a filosofia de desenvolvimento adotada pelos seus mantedores,
o compilador apresenta um código bastante maduro e otimizado, de difícil
legibilidade para desenvolvedores externos ao projeto. Em outras palavras, a
curva de aprendizado necessário para realizar uma contribuição a este projeto,
como é comum aos projetos GNU, é bastante significativa. Levando esta
dificuldade em conta, a razão pela qual o GCC foi escolhido como uma opção
viável para este trabalho foi uma refatoração em seu código que ocorreu com o
lançamento da versão 4.5. A partir desta versão, o GCC foi baseado em torno de
uma arquitetura de \textit{plugins}.

O uso de \textit{plugins} permite que os desenvolvedores consigam contribuir com
o projeto, adicionando novas funcionalidades, por exemplo, sem ter que modificar
o seu código original. Os \textit{plugins} são carregados dinamicamente (através
do suporte à bibliotecas dinâmicas no sistema operacional host), previamente
compilados. Isso diminui o tempo necessário para testar novas funcionalidades e
simplifica o trabalho do desenvolvedor, que não precisa mais entender
profundamente a arquitetura do compilador para contribuir com o projeto. Só é
preciso entender a interface de conexão do \textit{plugin} com o compilador.

A implementação de um novo backend para o GCC, tendo como alvo uma arquitetura
com processador RISCO, envolveria:

\begin{itemize}
\item Entender a arquitetura geral do compilador GCC, sem entrar em detalhes
muito específicos.

\item Estudar a nova arquitetura de plugins introduzida no GCC 4.5.

\item Determinar a opção mais viável para a implementação de um novo backend no
GCC. Podendo ser através da criação de um novo plugin ou a modificação direta do
código fonte do compilador.

\item Implementação do backend.
\end{itemize}

\subsection{O projeto LLVM e o compilador Clang}
\label{ss:llvm}

O projeto LLVM \cite{llvm_main_art} não é um compilador em si, mas um
\textit{framework} constituído por uma infraestrutura genérica para a construção
de compiladores para diversas linguagens e plataformas diferentes. Trata-se de
uma coleção de módulos reutilizáveis, implementando o estado da arte no que diz
respeito a pesquisa em compiladores. O LLVM deu um salto considerável em
popularidade nos últimos anos, e hoje em dia é amplamente utilizado tanto na
indústria como na pesquisa acadêmica. 

Inicialmente, o LLVM foi um projeto de pesquisa na Universidade de Illinois.
Desde então, o projeto cresceu e hoje serve como um nome comum a um conjunto de
subprojetos razoavelmente independentes. Para o escopo deste trabalho, dois são
relevantes: o \textit{núcleo LLVM} e o \textit{compilador Clang}. 

O núcleo LLVM é um conjunto de bibliotecas C++ que constituem todos os módulos
necessários para os passos de otimização e de geração de código em um compilador
moderno. Além disso, o LLVM inclui um repositório extensivo de passos de
otimização, assim como \textit{back-ends} de geração de código para todas as
arquiteturas mais populares. Os passos de transformação e geração de código
presentes no núcleo LLVM assumem que a linguagem de entrada é uma linguagem de
representação intermediária própria do projeto LLVM, denominada de
\textit{LLVM-IR}, ou \textit{LLVM Assembly Language}. Todos os compiladores que
utilizam o LLVM para as tarefas de geração de otimização e geração de código são
basicamente tradutores da sua linguagem de entrada particular para a LLVM-IR. A
partir do código fonte nesta linguagem, os módulos do núcleo LLVM se encarregam
de todo o processo de geração de código de máquina.

\abrv[SSA -- Static Single Assignment Form]

A LLVM-IR é uma linguagem assembly tipada, baseada na forma de atribuição
única estática (\textit{Static Single Assignment} – SSA), que provê uma
representação legível para humanos de código fonte. A IR é flexível, robusta e
baixo nível o bastante para ser o alvo de compiladores das mais diversas
linguagens. É uma representação leve, porém bastante expressiva e extensível ao
mesmo tempo. É um esforço claro na direção de uma linguagem intermediária
universal.

Considerando o que foi visto, a implementação do suporte a uma nova
arquitetura no LLVM envolveria:

\begin{itemize}
\item Estudo da especificação completa da LLVM-IR.

\item Estudo da arquitetura geral do núcleo LLVM. Entender o básico dos passos
de otimização e todos os detalhes dos módulos de geração de código.

\item Estudar os algoritmos genéricos de geração de código utilizados pelo LLVM
a fim de poder estendê-los, onde necessário, com as particularidades do RISCO.
Mais especificamente, tem-se: escolha de instruções, escalonamento de instruções
de acordo com o pipeline, alocação de registradores, inserção de código de
epílogo e prólogo, otimizações peephole no código de máquina final e finalmente
a emissão de código assembly propriamente dita.

\item Implementação do backend.
\end{itemize}

O trabalho de inclusão de um novo backend no núcleo LLVM poderá ser utilizado em
todos os compiladores que utilizam o LLVM para geração de código. O principal
deles é o Clang, um compilador de C, C++, Object-C e Object-C++ escrito sob a
infraestrutura LLVM. A maior vantagem da utilização do LLVM para este trabalho
seria que o seu sucesso teria como resultado o fato de que todos estes
compiladores passariam a ter suporte automático para geração de código para
plataformas RISCO. Além das linguagens suportadas pelo Clang, teríamos: Java,
Haskell, Ocaml, Ruby, Python, D, Scheme, Lisp, Ada, ML, entre outras. Uma outra
vantagem em favor do LLVM é a grande riqueza da sua documentação online, e a
alta legibilidade e qualidade do seu código fonte, facilitando o aprendizado.

\subsection{Otimizações}

Independentemente da escolha que será feita com relação ao compilador que será
estendido, em ambos os casos existe a infraestrutura necessária para o
desenvolvimento de novos passos de otimização de código dentro do processo de
compilação. Dentro do contexto da utilização do RISCO em sistemas embarcados,
faz sentido que o compilador a ser utilizado preze pela utilização de
otimizações de código voltadas a SE's. Será realizada, então, uma pesquisa com
relação a possibilidade de implementação de passos de otimização voltados a este
requisito.

Uma opção a ser considerada serão as otimizações de tamanho de código, que
visam a diminuição do tamanho do código assembly gerado. Isto traz a vantagem
imediata de que o código binário final terá um tamanho reduzido. Muitas vezes,
esta é uma necessidade inerente a plataforma embarcada sendo utilizada. Pode-se
estudar também técnicas de compressão de código após a compilação, tais como
apresentado em \cite{object_code_compression}.


\section{Montador}
\label{s:montador}

O montador (\textit{assembler}) para esta plataforma de desenvolvimento será uma
extensão de um trabalho já existente, conforme explicado na sessão
\ref{ss:trabalhos_existentes}. Esta ferramenta terá, obrigatoriamente, um
projeto modular, prezando pela facilidade de implementação de novos formatos de
saída.

O arquivo de saída do montador, neste trabalho, não tem uma especificação
fixa. Ele servirá de entrada para o dispositivo responsável pela execução do
código. Consequentemente, o seu formato depende da natureza do dispositivo. O
desenvolvimento desta ferramenta terá as seguintes fases:

\begin{itemize}
\item Especificação formal da linguagem assembly de entrada: a linguagem será
descrita por uma gramática livre de contexto, na forma de Backus-Naur
\cite{algol_report}. Terá um conjunto de instruções que obedece a um mapeamento
1:1 com o conjunto de instruções do processador RISCO. Além delas, a linguagem
ainda poderá incorporar funcionalidades de expansão de macros, a fim de
facilitar técnicas simples de meta-programação para aumentar a legibilidade do
código.
  
\item Geração de código binário para o simulador artificial: desenvolvimento do
backend necessário para que o montador consiga traduzir o assembly para o
formato binário de entrada do simulador.
  
\item Geração de código VHDL para simulação: desenvolvimento do backend
necessário para que o montador consiga gerar um arquivo VHDL que possa ser
incluído no projeto original do processador, contendo o código executável
correspondente. 
\end{itemize}


\section{Simulador}
\label{s:simulador}

Como visto nos modelos apresentados para o processo de desenvolvimento de
software para sistemas embarcados, o programador deve contar com um ambiente que
suporte simulações rápidas da execução de um programa. Caso tal suporte não
esteja presente, o desenvolvedor teria que carregar o código do protótipo na
memória de um dispositivo real, o que aumenta o tempo de projeto e o seu custo.
A existência de um simulador artificial em software flexibiliza o processo de
desenvolvimento, facilitando os testes e o uso de técnicas ágeis de
prototipagem.

Cabe mencionar como exemplo a linha de processadores MIPS, que é amplamente
utilizada para o ensino de arquitetura e organização de computadores
\cite{webmips}, assim como em sistemas embarcados \cite{mips_embedded}. Existem
diversos simuladores para este processador, tais como o apresentado em
\cite{mars}.

Pretendemos desenvolver um simulador em software, semelhante aos que foram
criados para o MIPS. Será necessário:

\begin{itemize}
\item Definir um formato de arquivo binário que irá conter o código executável.
Este formato de arquivo será uma simplificação de um formato real, como o ELF
utilizado nos sistemas Linux.

\item Definir as interfaces de apresentação do simulador. Isto é, como o
simulador irá apresentar os resultados do programa para o usuário. Inicialmente,
isto pode ser simplesmente uma saída em linha de comando. Futuramente, poderá
ser uma representação gráfica do estado atual do processador, por exemplo.

\item Implementação do simulador.
\end{itemize}


\section{Validação}

O trabalho aqui proposto consiste de uma grande quantidade de código a ser
desenvolvido, com uma considerável complexidade. Além do ferramental necessário,
alguns algoritmos de otimização também serão experimentados. Um projeto deste
porte faz que seja necessário projetar um esquema de testes capaz de auxiliar o 
desenvolvimento do trabalho.

Pretende-se montar um banco de testes, contendo programas simples em C e
assembly RISCO. Os casos de testes irão, eventualmente, ajudar a encontrar
defeitos nas ferramentas, além de ajudar a garantir a corretude do código
desenvolvido como um todo.


\section{Cronograma}

Para a coordenação do trabalho proposto neste documento, foi elaborado um
cronograma de atividades para o ano letivo de 2010, baseando-se nos limites
impostos pelo calendário acadêmico da UFRN. O cronograma será apresentado em
duas tabelas. A fig. \ref{fig:cronograma_implementacao} diz respeito ao
cronograma de todas as atividades de implementação deste trabalho, enquanto a
fig. \ref{fig:cronograma_escrita} engloba as atividades de escrita e defesa da
monografia.

\begin{figure}[hbt]
  \centering
  \includegraphics[scale=1]{images/cronograma-implementacao}
  \textsf{\caption{Cronograma das atividades de implementação}}
  \label{fig:cronograma_implementacao}
\end{figure}

\begin{figure}[hbt]
  \centering
  \includegraphics[scale=1]{images/cronograma-escrita}
  \textsf{\caption{Cronograma das atividades de escrita}}
  \label{fig:cronograma_escrita}
\end{figure}